package com.leetcode.LC_MED;

import java.util.ArrayList;

public class LC55 {
    public boolean canJump(int[] nums) {

        if (nums.length == 1) {
            return true;
        }

        boolean f = false;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == 0) {
                list.add(i);
                f = true;
            }
        }

        if (!f) {
            return true;
        }

        f = true;
        for (Integer integer : list) {
            f = f && toBoolean(integer, nums);
        }
        return f;
    }

    private boolean toBoolean(int a, int[] nums) {
        for (int i = 0; i < a; i++) {
            if (nums[i] > a - i) {
                return true;
            }
        }
        return false;
    }

    //贪心算法
    public boolean canJump2(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; i++) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }


}
